package dfs;

import java.util.ArrayList;
import java.util.List;

public class leetcode797所有可能的路径 {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(0);
        int n = graph.length;
        boolean[][] visited = new boolean[n][];
        for (int i = 0; i < n; i++) {
            visited[i] = new boolean[graph[i].length];
        }
        dfs(result, list, visited, graph, n, 0);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> list, boolean[][] visited, int[][] graph, int n, int node) {
        if (node == n - 1) {
            result.add(new ArrayList<>(list));
        } else {
            int length = graph[node].length;
            if (length == 0) {
                return;
            }
            for (int i = 0; i < length; i++) {
                visited[node][i] = true;
                list.add(graph[node][i]);
                dfs(result, list, visited, graph, n, graph[node][i]);
                list.remove(list.size() - 1);
                visited[node][i] = false;
            }
        }
    }
}
